package com.fr.lintcode;

import java.util.ArrayList;
import java.util.List;

public class Q90 {

    /*
     * @param A: an integer array
     * @param k: a postive integer <= length(A)
     * @param target: an integer
     * @return: A list of lists of integer
     */
	List<List<Integer>> rs = new ArrayList<>();
    public List<List<Integer>> kSumII(int[] A, int k, int target) {
        // write your code here
    	if(A == null || A.length < k) {
    		return rs;
    	}
    	int sum = 0;
    	int index = 0;
    	int count = 0;
    	boolean [] used = new boolean[A.length];
    	search(index, sum, count, used, A, k, target);
    	return rs;
    }
	private void search(int index, int sum, int count, boolean [] used, int[] a, int k, int target) {
		// TODO Auto-generated method stub
		if(count == k && sum == target) {
			save(used, a);
			return;
		}
		if(count > k || sum > target) {
			return;
		}
		for(int i = index; i < a.length; i ++) {
			if(!used[i]) {
				used[i] = true;
				count ++;
				sum = sum + a[i];
				search(i+1, sum, count, used, a, k, target);
				used[i] = false;
				count --;
				sum = sum - a[i];
			}
		}
		
	}
	private void save(boolean[] used, int[] a) {
		// TODO Auto-generated method stub
		List<Integer> list = new ArrayList<>();
		for(int i = 0; i < a.length; i++) {
			if(used[i]) {
				list.add(a[i]);
			}
		}
		rs.add(list);
	}


}
